//字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列： 
//
// 
// 序列中第一个单词是 beginWord 。 
// 序列中最后一个单词是 endWord 。 
// 每次转换只能改变一个字母。 
// 转换过程中的中间单词必须是字典 wordList 中的单词。 
// 
//
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中
//的 单词数目 。如果不存在这样的转换序列，返回 0。 
// 
//
// 示例 1： 
//
// 
//输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","lo
//g","cog"]
//输出：5
//解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
// 
//
// 示例 2： 
//
// 
//输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","lo
//g"]
//输出：0
//解释：endWord "cog" 不在字典中，所以无法进行转换。 
//
// 
//
// 提示： 
//
// 
// 1 <= beginWord.length <= 10 
// endWord.length == beginWord.length 
// 1 <= wordList.length <= 5000 
// wordList[i].length == beginWord.length 
// beginWord、endWord 和 wordList[i] 由小写英文字母组成 
// beginWord != endWord 
// wordList 中的所有字符串 互不相同 
// 
// Related Topics 广度优先搜索 哈希表 字符串 
// 👍 894 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class WordLadder {
    public static void main(String[] args) {
        String start = "leet";
        String end = "code";
        List<String> wordList = new ArrayList<>();
        wordList.add("lest");
        wordList.add("leet");
        wordList.add("lose");
        wordList.add("code");
        wordList.add("lode");
        wordList.add("robe");
        wordList.add("lost");
        new WordLadder().new Solution().ladderLength(start, end, wordList);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用双向bfs可以解决搜索空间爆炸的问题
         * 从两头开始搜索，遇到就是找到了
         * 使用java提供的双向队列deque（不知道为什么使用单向队列会超时）
         * 双向查找的时候如果根据当前word修改得到的新单词在另一个队列出现了，那就说明找到了
         * 否则的话将新单词添加到当前队列
         */
        String start;
        String end;
        List<String> list = new ArrayList<>();
        int len;
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (!wordList.contains(endWord)) return 0;
            len = beginWord.length();
            start = beginWord;
            end = endWord;
            list = wordList;
            int ans = bfs();
            return ans ==-1 ? 0 : ans+1;
        }
        public int bfs(){
            Deque<String> d1 = new ArrayDeque<>();//正向队列
            Deque<String> d2 = new ArrayDeque<>();//反向队列
            Map<String, Integer> m1 = new HashMap<>();
            Map<String, Integer> m2 = new HashMap<>();
            d1.addFirst(start);
            m1.put(start, 0);
            d2.addFirst(end);
            m2.put(end, 0);
            while (!d1.isEmpty()&&!d2.isEmpty()){
                int t;
                if (d1.size()<=d2.size()){//这里是为了保证均衡遍历，不让一边一直遍历下去
                    t = update(d1, m1, m2);
                }else t = update(d2,m2,m1);
                if (t != -1) return t;
            }
            return -1;
        }

        public int update(Deque<String> deque , Map<String,Integer> cur, Map<String,Integer> other){
            String temp = deque.pollFirst();
            for (int i = 0; i < len ; i++) {
                for (char j='a';j<='z' ;j++) {//替换字母得到新单词
                    String newWord = temp.substring(0, i)+j+temp.substring(i+1);
                    if (list.contains(newWord)){//只有当词典中存在此单词时才行
                        if (cur.containsKey(newWord)) continue;//这里说明本方向已经存在过此单词了
                        //这里说明在另一个方向上出现了此单词，两头可以连起来了
                        if (other.containsKey(newWord)) return cur.get(temp) + other.get(newWord)+1;
                        else {
                            //不然的话就添加到当前队列就行了
                            deque.addLast(newWord);
                            cur.put(newWord, cur.get(temp)+1);
                        }
                    }
                }
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
    /**
     * 使用的BFS遍历，就是时间复杂度太高了，将层数拼接在了字符串末尾
     * 一个set储存所有已经出现过的word
     * (我本来用了另一个set遍历了所有的字符串来存储出现的字母，但是真没必要)
     * 运行超时，但是我认为这个思路是可以的

     */
    public int myLadderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;
        int len = beginWord.length();
        Queue<String> queue = new LinkedList<>();
        Set<String> pastSet = new HashSet<>();
        queue.add(beginWord+1);
        pastSet.add(beginWord);
        while (!queue.isEmpty()){
            int count = Integer.parseInt(queue.peek().substring(len));
            String temp = queue.poll().substring(0,len);
            if (temp.equals(endWord)) return count;
            for (int i = 0; i < len; i++) {
                char c = temp.charAt(i);
                for (char j='a';j<='z' ;j++) {
                    if (j == c) continue;
                    String newWord = temp.substring(0, i)+j+temp.substring(i+1);
                    if (wordList.contains(newWord)&&!pastSet.contains(newWord)) {
                        queue.add(newWord + (count + 1));
                        pastSet.add(newWord);
                    }
                }
            }
        }
        return 0;
    }
}